/* 声明部分 */
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#ifdef _WIN32
#define strdup _strdup
#endif

// DAG节点结构
struct DAGNode {
    char op[10];
    char arg1[20];
    char arg2[20];
    char result[20];
    int visited;
    int id;
};

// 四元式结构
struct Quadruple {
    char op[10];
    char arg1[20];
    char arg2[20];
    char result[20];
};

// Loop结构
struct Loop {
    int header;
    int end;
};

void yyerror(const char *s);
int yylex(void);

/* 符号表结构 */
struct symbol {
    char *name;
    int type;    // 0: int, 1: float
    double value;
};

#define NSYMS 100     /* 符号表大小 */
struct symbol symtab[NSYMS];
int sym_count = 0;    /* 符号表中的符号数量 */

/* 四元式序列 */
struct Quadruple quadruples[100];
int quad_count = 0;

/* 存储优化后的四元式 */
struct Quadruple optimized_quads[100];
int optimized_quad_count = 0;

/* 基本块标记数组 */
char is_leader[100] = {0};

/* 全局变量 */
int temp_var_count = 0;  // 用于生成临时变量名

/* 函数声明 */
void print_quadruple(struct Quadruple q);
char* new_temp(void);
void generate_quad(char *op, char *arg1, char *arg2, char *result);
void print_quads(void);
struct DAGNode* find_dag_node(struct DAGNode *dag, int dag_size, char *op, char *arg1, char *arg2);
void build_dag(int start, int end, struct DAGNode *dag, int *dag_size);
void optimize_dag(struct DAGNode *dag, int dag_size);
void print_optimized_quads(void);
void find_loops(struct Loop* loops, int* num_loops);
void loop_invariant_code_motion(struct Loop* loop);
void strength_reduction(struct Loop* loop);
void induction_variable_elimination(struct Loop* loop);
void insert_quadruple(int position, const char* op, const char* arg1, const char* arg2, const char* result);

/* 生成标签 */
char* new_label() {
    static int label_count = 0;
    char* label = (char*)malloc(20);
    sprintf(label, "L%d", label_count++);
    return label;
}

/* 查找符号 */
struct symbol* lookup(char* name) {
    for(int i = 0; i < sym_count; i++) {
        if(strcmp(symtab[i].name, name) == 0) {
            return &symtab[i];
        }
    }
    return NULL;
}

/* 添加符号 */
void add_symbol(char* name, int type) {
    if(sym_count < NSYMS) {
        symtab[sym_count].name = strdup(name);
        symtab[sym_count].type = type;
        symtab[sym_count].value = 0;
        sym_count++;
    }
}

/* 函数实现 */
void print_quadruple(struct Quadruple q) {
    printf("%s, %s, %s, %s\n", q.op, q.arg1, q.arg2, q.result);
}

/* 生成临时变量名 */
char* new_temp() {
    static int temp_count = 0;
    char* temp = (char*)malloc(20);
    sprintf(temp, "t%d", temp_count++);
    return temp;
}

/* 添加四元式 */
void generate_quad(char *op, char *arg1, char *arg2, char *result) {
    strcpy(quadruples[quad_count].op, op);
    strcpy(quadruples[quad_count].arg1, arg1);
    strcpy(quadruples[quad_count].arg2, arg2);
    strcpy(quadruples[quad_count].result, result);
    quad_count++;
}

/* 输出所有四元式 */
void print_quads() {
    for (int i = 0; i < quad_count; i++) {
        print_quadruple(quadruples[i]);
    }
}

/* 构建基本块的DAG */
void build_dag(int start, int end, struct DAGNode *dag, int *dag_size) {
    *dag_size = 0;
    for (int i = start; i <= end && i < quad_count; i++) {
        if (strcmp(quadruples[i].op, "+") == 0 || strcmp(quadruples[i].op, "-") == 0 ||
            strcmp(quadruples[i].op, "*") == 0 || strcmp(quadruples[i].op, "/") == 0) {
            struct DAGNode *existing_node = find_dag_node(dag, *dag_size, quadruples[i].op, quadruples[i].arg1, quadruples[i].arg2);
            if (existing_node != NULL) {
                strcpy(existing_node->result, quadruples[i].result);
                continue;
            }
            strcpy(dag[*dag_size].op, quadruples[i].op);
            strcpy(dag[*dag_size].arg1, quadruples[i].arg1);
            strcpy(dag[*dag_size].arg2, quadruples[i].arg2);
            strcpy(dag[*dag_size].result, quadruples[i].result);
            dag[*dag_size].visited = 0;
            dag[*dag_size].id = *dag_size;
            (*dag_size)++;
        } else if (strcmp(quadruples[i].op, "=") == 0) {
            for (int j = 0; j < *dag_size; j++) {
                if (strcmp(dag[j].result, quadruples[i].arg1) == 0) {
                    strcpy(dag[j].result, quadruples[i].result);
                    break;
                }
            }
        }
    }
}

/* 查找DAG中已存在的节点 */
struct DAGNode* find_dag_node(struct DAGNode *dag, int dag_size, char *op, char *arg1, char *arg2) {
    for (int i = 0; i < dag_size; i++) {
        if (strcmp(dag[i].op, op) == 0 && strcmp(dag[i].arg1, arg1) == 0 && strcmp(dag[i].arg2, arg2) == 0) {
            return &dag[i];
        }
    }
    return NULL;
}

/* 优化DAG，生成优化后的四元式 */
void optimize_dag(struct DAGNode *dag, int dag_size) {
    optimized_quad_count = 0;
    for (int i = 0; i < dag_size; i++) {
        if (strlen(dag[i].op) > 0) {
            strcpy(optimized_quads[optimized_quad_count].op, dag[i].op);
            strcpy(optimized_quads[optimized_quad_count].arg1, dag[i].arg1);
            strcpy(optimized_quads[optimized_quad_count].arg2, dag[i].arg2);
            strcpy(optimized_quads[optimized_quad_count].result, dag[i].result);
            optimized_quad_count++;
        }
    }
}

/* 打印优化后的四元式 */
void print_optimized_quads() {
    for (int i = 0; i < optimized_quad_count; i++) {
        printf("    ");
        print_quadruple(optimized_quads[i]);
    }
}

/* 循环识别 */
void find_loops(struct Loop* loops, int* num_loops) {
    *num_loops = 0;
    
    // 遍历所有四元式，查找循环结构
    for (int i = 0; i < quad_count; i++) {
        // 查找条件跳转指令
        if (strcmp(quadruples[i].op, "<") == 0 || 
            strcmp(quadruples[i].op, ">") == 0 ||
            strcmp(quadruples[i].op, "<=") == 0 ||
            strcmp(quadruples[i].op, ">=") == 0) {
            
            // 查找后续的goto指令
            for (int j = i + 1; j < quad_count; j++) {
                if (strcmp(quadruples[j].op, "goto") == 0) {
                    // 找到一个循环
                    loops[*num_loops].header = i;
                    loops[*num_loops].end = j;
                    (*num_loops)++;
                    printf("Found loop from L%d to L%d\n", i, j);
                    break;
                }
            }
        }
    }
}

/* 循环不变代码外提 */
void loop_invariant_code_motion(struct Loop* loop) {
    printf("\nLoop Invariant Code Motion:\n");
    
    // 显示循环原始代码
    printf("Original loop code:\n");
    for (int i = loop->header; i <= loop->end; i++) {
        printf("    ");
        print_quadruple(quadruples[i]);
    }
    
    // 遍历循环体中的每条指令
    for (int i = loop->header; i <= loop->end; i++) {
        // 检查是否是运算指令
        if (strcmp(quadruples[i].op, "*") == 0 || 
            strcmp(quadruples[i].op, "/") == 0 ||
            strcmp(quadruples[i].op, "+") == 0 ||
            strcmp(quadruples[i].op, "-") == 0) {
            
            bool is_invariant = true;
            
            // 检查操作数是否在循环中被修改
            for (int j = loop->header; j <= loop->end; j++) {
                if (strcmp(quadruples[j].result, quadruples[i].arg1) == 0 ||
                    strcmp(quadruples[j].result, quadruples[i].arg2) == 0) {
                    is_invariant = false;
                    break;
                }
            }
            
            // 如果是循环不变代码，移动到循环前
            if (is_invariant) {
                printf("Found invariant code at L%d: ", i);
                print_quadruple(quadruples[i]);
                
                // 保存当前四元式
                struct Quadruple temp = quadruples[i];
                
                // 移除原位置的四元式
                for (int j = i; j < quad_count - 1; j++) {
                    quadruples[j] = quadruples[j + 1];
                }
                quad_count--;
                
                // 在循环前插入
                insert_quadruple(loop->header, temp.op, temp.arg1, temp.arg2, temp.result);
                
                // 更新循环范围
                loop->end--;
                i--;  // 重新检查当前位置
            }
        }
    }
    
    // 显示优化后的循环代码
    printf("\nOptimized loop code:\n");
    for (int i = loop->header; i <= loop->end; i++) {
        printf("    ");
        print_quadruple(quadruples[i]);
    }
}

/* 强度削弱 */
void strength_reduction(struct Loop* loop) {
    printf("\nStrength Reduction:\n");
    
    // 显示原始代码
    printf("Original code:\n");
    for (int i = loop->header; i <= loop->end; i++) {
        printf("    ");
        print_quadruple(quadruples[i]);
    }
    
    // 遍历循环体中的每条指令
    for (int i = loop->header; i <= loop->end; i++) {
        // 查找乘法运算
        if (strcmp(quadruples[i].op, "*") == 0) {
            // 检查是否是与2的幂相乘
            if (quadruples[i].arg2[0] >= '0' && quadruples[i].arg2[0] <= '9') {
                int value = atoi(quadruples[i].arg2);
                if ((value & (value - 1)) == 0) {  // 是2的幂
                    int shift = 0;
                    while (value > 1) {
                        shift++;
                        value >>= 1;
                    }
                    
                    printf("Converting multiplication at L%d to shift: ", i);
                    print_quadruple(quadruples[i]);
                    
                    sprintf(quadruples[i].arg2, "%d", shift);
                    strcpy(quadruples[i].op, "<<");
                }
            }
        }
    }
    
    // 显示优化后的代码
    printf("\nOptimized code:\n");
    for (int i = loop->header; i <= loop->end; i++) {
        printf("    ");
        print_quadruple(quadruples[i]);
    }
}

/* 归纳变量优化 */
void induction_variable_elimination(struct Loop* loop) {
    printf("\nInduction Variable Elimination:\n");
    
    // 显示原始代码
    printf("Original code:\n");
    for (int i = loop->header; i <= loop->end; i++) {
        printf("    ");
        print_quadruple(quadruples[i]);
    }
    
    // 遍历循环体查找基本归纳变量
    for (int i = loop->header; i <= loop->end; i++) {
        if (strcmp(quadruples[i].op, "+") == 0 &&
            strcmp(quadruples[i].arg2, "1") == 0) {
            printf("Found basic induction variable at L%d: %s\n", i, quadruples[i].result);
            
            // 查找该归纳变量的相关运算
            for (int j = loop->header; j <= loop->end; j++) {
                if (strcmp(quadruples[j].arg1, quadruples[i].result) == 0 ||
                    strcmp(quadruples[j].arg2, quadruples[i].result) == 0) {
                    printf("Found related operation at L%d: ", j);
                    print_quadruple(quadruples[j]);
                }
            }
        }
    }
    
    // 显示优化后的代码
    printf("\nOptimized code:\n");
    for (int i = loop->header; i <= loop->end; i++) {
        printf("    ");
        print_quadruple(quadruples[i]);
    }
}

/* 插入四元式 */
void insert_quadruple(int position, const char* op, const char* arg1, const char* arg2, const char* result) {
    // 将position之后的四元式向后移动一位
    for (int i = quad_count; i > position; i--) {
        quadruples[i] = quadruples[i-1];
    }
    
    // 在position处插入新的四元式
    strcpy(quadruples[position].op, op);
    strcpy(quadruples[position].arg1, arg1);
    strcpy(quadruples[position].arg2, arg2);
    strcpy(quadruples[position].result, result);
    
    quad_count++;
}

%}

/* Bison声明 */
%union {
    double num;           /* 数字值 */
    char *str;           /* 标识符名称 */
    char *temp;          /* 临时变量名 */
    struct {
        char *true_label;
        char *false_label;
        char *next_label;
    } labels;
}

/* Token definitions */
%token EOL
%token UMINUS

/* 运算符优先级和结合性 */
%left GT LT EQ NE GE LE
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

/* 终结符声明 */
%token <num> NUMBER
%token <str> IDENTIFIER
%token ASSIGN INT FLOAT IF ELSE WHILE
%token SEMICOLON LPAREN RPAREN LBRACE RBRACE

/* 非终结符类型声明 */
%type <temp> expr term factor
%type <labels> condition
%type <str> declaration
%type <temp> assignment

%%

program:
    statement_list    { 
        printf("Program parsed successfully\n"); 
        printf("Semantic analysis completed\n");
        printf("Quadruples generated:\n");
        print_quads();
        
        printf("Parsing completed successfully!\n");
        printf("Generated Quadruples:\n");
        for (int i = 0; i < quad_count; i++) {
            print_quadruple(quadruples[i]);
        }
    }
    ;

statement_list:
    statement
    | statement_list statement
    | statement_list EOL
    ;

statement:
    declaration SEMICOLON
    | assignment SEMICOLON
    | if_statement
    | while_statement
    | block
    | EOL
    ;

block:
    LBRACE statement_list RBRACE
    | LBRACE RBRACE
    ;

declaration:
    INT IDENTIFIER    { 
        printf("Semantic analysis: declaring integer variable %s\n", $2);
        add_symbol($2, 0);
        $$ = $2;
    }
    | FLOAT IDENTIFIER {
        printf("Semantic analysis: declaring float variable %s\n", $2);
        add_symbol($2, 1);
        $$ = $2;
    }
    ;

assignment:
    IDENTIFIER ASSIGN expr   { 
        printf("Semantic analysis: assigning to variable %s\n", $1);
        struct symbol* sym = lookup($1);
        if(sym != NULL) {
            generate_quad("=", $3, "", $1);
            $$ = $1;
        } else {
            yyerror("Undefined variable");
            $$ = "";
        }
    }
    ;

condition:
    expr GT expr     {
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad(">", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    | expr LT expr   {
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad("<", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    | expr GE expr   {
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad(">=", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    | expr LE expr   {
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad("<=", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    | expr EQ expr   {
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad("==", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    | expr NE expr   {
        $$.true_label = new_label();
        $$.false_label = new_label();
        generate_quad("!=", $1, $3, $$.true_label);
        generate_quad("goto", "", "", $$.false_label);
    }
    ;

if_statement:
    IF LPAREN condition RPAREN statement {
        generate_quad("label", "", "", $3.true_label);
        generate_quad("label", "", "", $3.false_label);
    }
    | IF LPAREN condition RPAREN statement ELSE statement {
        char* end_label = new_label();
        generate_quad("label", "", "", $3.true_label);
        generate_quad("goto", "", "", end_label);
        generate_quad("label", "", "", $3.false_label);
        generate_quad("label", "", "", end_label);
    }
    ;

while_statement:
    WHILE LPAREN condition RPAREN statement {
        char* start_label = new_label();
        generate_quad("label", "", "", start_label);
        generate_quad("label", "", "", $3.true_label);
        generate_quad("goto", "", "", start_label);
        generate_quad("label", "", "", $3.false_label);
    }
    ;

expr:
    term                { $$ = $1; }
    | expr '+' term     { 
        char* temp = new_temp();
        generate_quad("+", $1, $3, temp);
        $$ = temp;
    }
    | expr '-' term     { 
        char* temp = new_temp();
        generate_quad("-", $1, $3, temp);
        $$ = temp;
    }
    ;

term:
    factor              { $$ = $1; }
    | term '*' factor   { 
        char* temp = new_temp();
        generate_quad("*", $1, $3, temp);
        $$ = temp;
    }
    | term '/' factor   { 
        char* temp = new_temp();
        generate_quad("/", $1, $3, temp);
        $$ = temp;
    }
    ;

factor:
    NUMBER          { 
        char* temp = new_temp();
        char num_str[20];
        sprintf(num_str, "%g", $1);
        generate_quad("=", num_str, "", temp);
        $$ = temp;
    }
    | IDENTIFIER    { 
        printf("Semantic analysis: reading variable %s\n", $1);
        struct symbol* sym = lookup($1);
        if(sym != NULL) {
            char* temp = new_temp();
            generate_quad("=", $1, "", temp);
            $$ = temp;
        } else {
            yyerror("Undefined variable");
            $$ = "";
        }
    }
    | LPAREN expr RPAREN    { $$ = $2; }
    | '-' factor %prec UMINUS   { 
        char* temp = new_temp();
        generate_quad("-", "0", $2, temp);
        $$ = temp;
    }
    ;

%%

void yyerror(const char *s) {
    fprintf(stderr, "Error: %s\n", s);
}

int main(void) {
    printf("Enter your program (press Ctrl+D to end):\n");
    yyparse();
    
    printf("\n=== Original Quadruples ===\n");
    print_quads();

    printf("\n=== Basic Block Analysis ===\n");
    // 标记基本块的起始位置
    is_leader[0] = 1; // 第一个四元式是基本块的起始
    for (int i = 0; i < quad_count; i++) {
        if (strcmp(quadruples[i].op, "label") == 0) {
            is_leader[i+1] = 1;
        } else if (strcmp(quadruples[i].op, "goto") == 0 || 
                   strcmp(quadruples[i].op, "if==0") == 0) {
            is_leader[i+1] = 1;
        }
    }

    // 存储优化后的四元式
    struct Quadruple final_optimized[100];
    int final_opt_count = 0;

    // 基本块划分和DAG优化
    printf("\n=== Basic Blocks and DAG Optimization ===\n");
    int block_start = 0;
    for (int i = 0; i <= quad_count; i++) {
        if (i == quad_count || is_leader[i]) {
            if (i > block_start) {
                printf("\nBasic Block %d:\n", block_start);
                printf("Block Range: L%d - L%d\n", block_start, i - 1);
                printf("Original instructions:\n");
                for (int j = block_start; j < i; j++) {
                    printf("    "); print_quadruple(quadruples[j]);
                }
                
                // 对当前基本块进行DAG优化
                struct DAGNode dag[100];
                int dag_size = 0;
                build_dag(block_start, i-1, dag, &dag_size);
                optimize_dag(dag, dag_size);
                
                if (optimized_quad_count < i - block_start) {
                    printf("After DAG optimization:\n");
                    for (int j = 0; j < optimized_quad_count; j++) {
                        printf("    ");
                        print_quadruple(optimized_quads[j]);
                        // 保存到最终优化结果
                        final_optimized[final_opt_count++] = optimized_quads[j];
                    }
                } else {
                    printf("No DAG optimizations possible for this block\n");
                    // 如果没有优化，保留原始四元式
                    for (int j = block_start; j < i; j++) {
                        final_optimized[final_opt_count++] = quadruples[j];
                    }
                }
            }
            block_start = i;
        }
    }

    // 循环优化
    printf("\n=== Loop Optimization Analysis ===\n");
    struct Loop loops[100];
    int num_loops = 0;
    find_loops(loops, &num_loops);

    if (num_loops > 0) {
        struct Quadruple loop_optimized[100];
        int loop_opt_count = 0;
        
        for (int i = 0; i < num_loops; i++) {
            printf("\nLoop %d Analysis:\n", i + 1);
            printf("Loop Range: L%d - L%d\n", loops[i].header, loops[i].end);
            
            // 显示循环原始代码
            printf("\nOriginal Loop Code:\n");
            for (int j = loops[i].header; j <= loops[i].end; j++) {
                printf("    "); print_quadruple(final_optimized[j]);
            }
            
            // 循环不变代码外提
            printf("\nLoop Invariant Code Motion Analysis:\n");
            loop_invariant_code_motion(&loops[i]);
            
            // 强度削弱
            printf("\nStrength Reduction Analysis:\n");
            strength_reduction(&loops[i]);
            
            // 归纳变量优化
            printf("\nInduction Variable Analysis:\n");
            induction_variable_elimination(&loops[i]);
        }
    } else {
        printf("No loops found in the code.\n");
    }

    // 输出最终优化结果
    printf("\n=== Final Optimized Quadruples ===\n");
    printf("(After both DAG and Loop Optimizations)\n");
    for (int i = 0; i < final_opt_count; i++) {
        printf("L%d: ", i);
        print_quadruple(final_optimized[i]);
    }

    return 0;
}